A problem that is common to all data communications technologies is the corruption of data. The likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful. Error correcting codes are employed on data transmission and data storage channels to correct or avoid bit errors due to noise and other channel imperfections. As applied to information theory and coding, an error-correcting code is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. Error correcting codes are used to detect and/or correct single-bit errors, double-bit errors, and multi-bit errors.
In information theory, the Shannon-Hartley theorem states the maximum amount of error-free digital data that can be transmitted over a communication link with a specified bandwidth in the presence of noise interference. The Shannon limit of a communications channel is the theoretical maximum information transfer rate of the channel.
The Shannon-Hartley theorem describes the maximum possible efficiency of error-correcting methods versus levels of noise interference and data corruption. This theorem does not describe how to construct the error-correcting method. Instead, the theorem indicates the maximum efficiency of the error-correcting method used.
Two main classes of error-correcting codes are block codes and convolutional codes. Convolutional codes operate on serial data, one or a few bits at a time. Block codes operate on relatively large (typically, up to a couple of hundred bytes) message blocks. There are a number of conventional convolutional and block codes currently in use, and a number of algorithms for decoding the received coded information sequences to recover the original data.
Error correction, using an error correcting code, improves the reliability of communication systems and devices. In conventional encoding methods, an encoder at the transmission end of a communication encodes an input word, such as a block or vector of a given length, to produce a codeword associated with the error correction code. A conventional transmitter stores in its memory one or a small number of algorithms to produce codewords of a certain code. At the receiving end of the communication, a decoder decodes the received codeword to generate an estimation of the original input word.
A channel code is a set of codewords (e.g., binary vectors) which are easily distinguishable from one another, even in the presence of noise, so that transmission errors are avoided. To facilitate encoding and decoding, binary linear codes are generally used. This means that the set of codewords C is a certain k-dimensional subspace of the vector space Fn2 of binary n-tuples over the binary field F2={0, 1}. Thus, there is a basis B={g0, . . . gk-1} which spans C so that each cεC may be written as c=uOgO+u1g1+ . . . +uk-1gk-1 for some {ui} in F2. More compactly, c=uG where u={u0, u1, . . . , uk-1} is the k-bit information word and G is the k×n generator matrix whose rows are the vectors {gi} (as is conventional in coding, all vectors are row vectors). Further, the (n-k) dimensional null space C⊥ of G is spanned by the basis B⊥={h0, h1, . . . , hn-k-1}. Thus, for each cεC, cHT=0, where H is the (n−k)×n parity-check matrix whose rows are the vectors {hi}. The parity-check matrix H performs m=n−k separate parity checks on a received word.
A low-density parity-check code (LDPC) is a linear block code for which the parity-check matrix H has a low density of I 's. The sparseness of an LDPC code's H matrix makes it amenable to a near-optimal decoding procedure called belief propagation. Using Low Density Parity Check (LDPC) codes for error correction generates parity check codes that have a predetermined number of elements having a value of one in rows and columns of the parity check codes. Parity data is then generated based on the parity check codes. That is, in the coding method based on the LDPC codes, a parity check matrix H having a predetermined number of elements that include a value of one in its rows and columns is formed, and a codeword x satisfying the equation Hx=0 is obtained. The codeword x includes original data and parity data.
There are several known techniques for generating the generator matrix G. These include Hamming codes, BCH codes, and Reed-Solomon codes. Another known code is a low density parity check (LDPC) code, developed by Gallager in the early 1960's. With block codes, a parity check matrix H of size (n−1)×n exists such that the transpose of H (e.g., HT), when multiplied by G, produces a null set, or G×HT=0. The decoder multiplies the received codeword c (m×G=c) by the transpose of H, e.g., c×HT. The result, often referred to as the “syndrome,” is a 1×(n−k) matrix of all 0's if c is a valid codeword.
Virtually all LDPC code design procedures involve specification of the H matrix after which an encoding procedure is devised. A generator matrix G may be obtained from H via Gauss-Jordan elimination, but the resulting encoding operation via c=uG is still too complex for long codes. To simplify the operation, a technique has been proposed in which encoding is performed directly from H. Alternatively, cyclic and quasi-cyclic (QC) LDPC codes have been proposed which lend themselves to lower-complexity shift-register based encoder implementations. The low-complexity advantage derives from the fact that the H matrix is composed of circulant submatrices. What is needed is a simpler method of utilizing LDPC codes in encoding procedures. What is also needed is a simpler method of generating a G matrix to be used in such encoding procedures.